package demo03;

import java.util.Random;

//快速排序(分三块)
class Solution {
    public int[] sortArray(int[] nums) {
        int l = 0 ,r = nums.length-1;
        qsort(nums,l,r);
        return nums;
    }
    public void qsort(int[] nums,int l,int r){
        if(l>=r) return;
        int n = new Random().nextInt(r-l+1)+l;
        int key = nums[n];
        int left = l-1,right = r+1,i = l;
        //主逻辑
        while(i<right){
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    public void swap(int[] nums,int left,int right){
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }
}